// https://www.lintcode.com/problem/burst-balloons/description

class Solution {
public:
    /**
     * @param nums: A list of integer
     * @return: An integer, maximum coins
     */
    int maxCoins(vector<int> &nums) {
        nums.insert(nums.begin(), 1);
        nums.insert(nums.end(), 1);
        int n = nums.size();
        vector<vector<int>> res(n, vector<int>(n)); //res[i][j]不算边界，dp里面也不算，所以j>=i + 2
        for (int i = 0; i < n - 1; ++i) {
            res[i][i+1] = 0; 
        }
       
        for (int len = 3; len < n + 1; ++len)
        {
            for (int i = 0; i < n - len + 1; ++i)
            {
                // for (int w = 1; w < len; ++w)
                for (int k = i + 1; k < i + len - 1; ++k)
                {
                    res[i][i + len - 1] = max(res[i][i + len - 1], res[i][k] + nums[i] * nums[k] * nums[i + len - 1] + res[k][i + len - 1]);
                }
            }
        }
        
          
        return res[0][n - 1];
    }
};

// class Solution {
// public:
//     /**
//      * @param nums: A list of integer
//      * @return: An integer, maximum coins
//      */
//     vector<int> init(vector<int> &nums) {    		//初始化数组，头部和尾部插入1
//         vector<int> temp(nums.size() + 2);
//         temp[0] = 1;
//         for(int i = 1; i < temp.size() - 1; i++){
//             temp[i] = nums[i - 1];
//         }
//         temp[temp.size() - 1] = 1;
//         return temp;
//     } 
//     int maxCoins(vector<int> &nums) {
//         // write your code here
//         if (nums.size() == 0){
//             return 0;
//         }
//         nums = init(nums);
//         int dp [nums.size()][nums.size()];
//         memset(dp, 0 ,sizeof(dp) );

//         for (int i = nums.size() - 1; i >= 0; i--) {
//             for (int j = i + 2; j < nums.size(); j++) {
//                 for (int k = i + 1; k < j; k++) {
//                     dp[i][j] = max(dp[i][j], dp[i][k] +  dp[k][j] + nums[i] * nums[k] * nums[j]);		//状态转移利用小区间最优解更新大区间
//                 }
//             }
//         }
        
//         return dp[0][nums.size() - 1];
//     }
// };